package com.arrays.a2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class FourSum {

    /*
    方法1. 时间复杂度较高 耗时
     */
    public static List<List<Integer>> fourSum1(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    for (int m = k + 1; m < nums.length; m++) {
                        if (nums[i] + nums[j] + nums[k] + nums[m] == target) {
                            List<Integer> ans = new ArrayList<>();
                            Collections.addAll(ans, nums[i], nums[j], nums[k], nums[m]);
                            Collections.sort(ans);
                            if (!res.contains(ans)) {
                                res.add(ans);
                            }
                        }
                    }
                }
            }
        }
        return res;
    }

    /*
    方法2. 利用双层循环和双指针
     */
    //判断时每次循环都计算四数之和是否符合要求
    public List<List<Integer>> fourSum2(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length;
        Arrays.sort(nums);

        for (int i = 0; i < len - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < len - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int l = j + 1;
                int r = len - 1;
                while (l < r) {
                    int sum = nums[i] + nums[j] + nums[l] + nums[r];
                    if (sum == target) {
                        ArrayList<Integer> tmp = new ArrayList<>();
                        Collections.addAll(tmp, nums[i], nums[j], nums[l], nums[r]);
                        res.add(tmp);
                        l++;
                        r--;
                        while (l < r && nums[l] == nums[l - 1]) {
                            l++;
                        }
                        while (l < r && nums[r] == nums[r + 1]) {
                            r--;
                        }
                    } else if (sum < target) {
                        l++;
                    } else {
                        r--;
                    }
                }

            }
        }
        return res;

    }

    //判断时 先计算出已确定的两个和，再判断双指针指向的和是否符合要求
    public static List<List<Integer>> fourSum3(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length;
        Arrays.sort(nums);

        for (int i = 0; i < len - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {//去重
                continue;
            }
            for (int j = i + 1; j < len - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {//去重
                    continue;
                }
                int l = j + 1;
                int r = len - 1;
                int t = target - nums[i] - nums[j];
                while (l < r) {
                    int cur = nums[l] + nums[r];
                    if (cur < t) {
                        l++;
                    } else if (cur > t) {
                        r--;
                    } else {
                        List<Integer> ans = new ArrayList<>();
                        Collections.addAll(ans, nums[i], nums[j], nums[l], nums[r]);
                        res.add(ans);
                        l++;
                        r--;
                        //去重 不越界且 当 l 等于它之前（左边）的一个数，说明已经被枚举过了
                        while (l < r && nums[l] == nums[l - 1]) {
                            l++;
                        }
                        //去重 不越界且 当 r 等于它右边的一个数，说明已经被枚举过了
                        while (l < r && nums[r] == nums[r + 1]) {
                            r--;
                        }
                    }
                }
            }
        }
        return res;

    }


    /*
    优化
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        if (len < 4) {
            return res;
        }
        long min4 = (long) nums[0] + nums[1] + nums[2] + nums[3];
        long max3 = (long) nums[len - 1] + nums[len - 2] + nums[len - 3];
        long sum3 = 0;

        for (int i = 0; i < len - 3; i++) {
            if (min4 > target) {//最小的4个数的和大于目标值
                break;
            }
            if (i + 4 < len) {
                min4 = min4 - nums[i] + nums[i + 4];//向右滑动更新区间和
            }
            if (i > 0 && nums[i] == nums[i - 1]) {//去重
                continue;
            }

            if (max3 + nums[i] < target) {//第一个元素+最大的三个数的和小于目标值
                continue;
            }
            //如果第一个数确定，并加上后面三个连续数的和小于target,结束循环
            sum3 = (long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3];


            for (int j = i + 1; j < len - 2; j++) {
                if (sum3 > target) {
                    break;
                }
                if (j + 3 < len) {
                    sum3 = sum3 - nums[j] + nums[j + 3];//更新区间和
                }
                if (j > i + 1 && nums[j] == nums[j - 1]) {//去重
                    continue;
                }
                int l = j + 1;
                int r = len - 1;
                /*第二层循环时，可以确定nums[i]+nums[j]
                        可以先计算出前两数和，再判断 双指针指向的和是否满足要求
                        这样 先确定已知的两个和 再判断 双指针的和 可以比每次都计算出四个数之和要稍快些
                 */
                int t = target - nums[i] - nums[j];

                while (l < r) {
                    int cur = nums[l] + nums[r];
                    if (cur < t) {
                        l++;
                    } else if (cur > t) {
                        r--;
                    } else {
                        List<Integer> ans = new ArrayList<>();
                        Collections.addAll(ans, nums[i], nums[j], nums[l], nums[r]);
                        res.add(ans);
                        l++;
                        r--;
                        //去重 不越界且 当 l 等于它之前（左边）的一个数，说明已经被枚举过了
                        while (l < r && nums[l] == nums[l - 1]) {
                            l++;
                        }
                        //去重 不越界且 当 r 等于它右边的一个数，说明已经被枚举过了
                        while (l < r && nums[r] == nums[r + 1]) {
                            r--;
                        }
                    }
                }
            }
        }
        return res;
    }


    public static void main(String[] args) {
        int[] a = {1, 0, -1, 0, -2, 2};
        List<List<Integer>> lists = fourSum1(a, 0);
        System.out.println(lists);

    }
}
